package th.retrofit.lib;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Node {

    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }

    public String toString() {
        List<Node> nodes = new ArrayList<>();
        List<Node> children = new ArrayList<>();
        nodes.add(this);
        children.add(left);
        children.add(right);
        while (!isEmpty(children)) {
            List<Node> temp = new ArrayList<>(children);
            children.clear();
            for (Node node : temp) {
                if (node != null) {
                    children.add(node.left);
                    children.add(node.right);
                }
            }
            nodes.addAll(temp);
        }
        StringBuilder builder = new StringBuilder();
        builder.append('[');
        int size = nodes.size();
        for (int i = 0; i < size; i++) {
            Node node = nodes.get(i);
            if (node != null) {
                builder.append(node.val);
            } else if (i != size - 1){
                builder.append("null");
            }
            if (i != size - 1) {
                builder.append(",");
            }
        }
        builder.append(']');
        if (builder.charAt(builder.length() - 2) == ',') {
            builder.deleteCharAt(builder.length() - 2);
        }
        return builder.toString();
    }

    private boolean isEmpty(List<Node> list) {
        if (list.isEmpty()) return true;
        for (Node node : list) {
            if (node != null) return false;
        }
        return true;
    }

    public static Node array2Tree(Integer... arr) {
        Node[] nodes = new Node[arr.length];
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != null) {
                nodes[i] = new Node(arr[i]);
            } else {
                nodes[i] = null;
            }
        }
        return array2Tree(nodes);
    }

    public static Node array2Tree(Node... arr) {
        int size = arr.length;
        Node head = arr[0];
        int index = 1;
        List<Node> pre = new LinkedList<>();
        pre.add(head);
        while (index < size) {
            List<Node> temp = new LinkedList<>();
            for (Node node: pre) {
                if (node != null && index < size) {
                    node.left = arr[index++];
                    temp.add(node.left);
                    if (index < size) {
                        node.right = arr[index++];
                        temp.add(node.right);
                    }
                }
            }
            pre.clear();
            pre.addAll(temp);
        }
        return head;
    }
    
}
